Problem statement: zenit13ckd
D: SimCity |
25 bodov | Časový limit: 100 ms |
Každé mesto, ktoré v SimCity prosperuje si koleduje o katastrofu. A keď už bol úspech metropoly
Baranovce príliš markantný, tak si Godzilla-style-ultimate-killer monster menom Bowser povedal, že
je najvyšší čas ísť si trošku pošľapať. Môžeme len dúfať, že si autor mesta svoje dielo uložil.
Bowserovi samozrejme nevadí prejsť ani po vodnej ploche, ani po žiadnom type budovy. Najviac ho ale
zaujímajú políčka s obytnými domami, pretože šľapanie po ľuďoch mu spôsobuje na chodidlách príjemné pocity.
Mapa mesta má obdĺžnikový pôdorys. Plochu môžeme rozdeliť na malé štvorčeky, na každom z nich je
jedna budova. Na prvom riadku vstupu sú dve čísla R a S (1 ≤ R,S ≤ 100) - rozmery pôdorysu.
Na každom z ďalších R riadkov je S znakov - popis mesta. Pre jednoduchosť, znaky na mape môžu byť R (rezidencia)
alebo . (iná stavba, prázdne políčko alebo vodná plocha).
Bowser sa rozhodol, že spraví jeden šikmý prechod naprieč mestom. Na začiatku sa objaví na niektorom z okrajových políčok a potom pôjde
zvoleným smerom, až kým neopustí pôdorys mesta, čím jeho deštrukčné aktivity skončia. Trasa Bowserovho prechodu teda môže vyzerať napríklad nasledovne:
.B... ...B. ..... B....
..B.. ....B ....B .....
...B. ..... ...B. .....
....B ..... ..B.. .....
Zistite, cez koľko najviac R Bowser prejde, ak vhodne zvolí počiatočné políčko a smer.
>
Príklady:
| |
4 5
.RR..
.RR.R
.....
....R
|
| |
Jediná možnosť ako dosiahnuť tri je
.B...
..B..
...B.
....B
| |
2 14
R.R.RR...R....
R......R...RRR
|
| |